package com.tgy.algorithm._经典题目01;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 请实现如下结构
 * TopRecord{
 *  public TopRecord(int k):构造时事先指定好K的大小，构造后就固定不变了
 *  public void add(String str):向该结构中加入一
 *  public List<String>top():返回之前加入的所有字符串中，词频最大的K个
 *  }
 * 要求
 * add方法复杂度O(log k);
 * top方法，复杂度O(K)
 */

class TopRecord {
    private NodeTime[] values;
    private int size;
    private int cap;

    private HashMap<String,NodeTime> container;
    private HashMap<String,Integer> locations;
    class NodeTime {
        String key;
        int times;
        NodeTime(String key, int times) {
            this.key = key;
            this.times = times;
        }
    }

    public TopRecord(int k) {
        this.cap = k;
        this.values = new NodeTime[k];
        this.size = 0;
        this.container = new HashMap<>();
        this.locations = new HashMap<>();
    }

    public void add(String key) {

        NodeTime nodeTime = null;
        if (container.containsKey(key)) {
            nodeTime = container.get(key);
            nodeTime.times++;
        }else {
            nodeTime = new NodeTime(key, 1);
            container.put(key,nodeTime);
        }

        int index = -1;
        if (locations.containsKey(key)) {
            index = locations.get(key);
        }else {
            locations.put(key,-1);
        }

        if (index == -1) {
            if (this.size < this.cap ) {
                offer(nodeTime);
            }else {
                if (this.peek().times < nodeTime.times) {
                    this.locations.put(this.values[0].key,-1);
                    this.values[0] = nodeTime;
                    this.locations.put(key,0);
                    heapfy(0);
                }
            }

        }else {
            heapfy(index);
        }

    }

    public List<String> top() {

        ArrayList<String> rets = new ArrayList<>();
        for (int i = this.size - 1; i >= 0; i--) {
            rets.add(values[i].key);
        }
        return rets;
    }

    private void offer(NodeTime node) {
        this.values[this.size] = node;
        this.locations.put(node.key,this.size);
        this.heapInsert(this.size++);
    }

    private NodeTime peek() {
        return this.values[0];
    }

    private void heapfy(int index) {
        // 往下走
//        int left = (index << 1) + 1;
//        int right = left + 1;
        while (index < size) {
            int left = (index << 1) + 1;
            if (left >= size) {
                break;
            }
            int minIdx = left;
            if (left + 1 < size && values[left].times > values[left+1].times) {
                minIdx = left+1;
            }

            if (values[minIdx].times < values[index].times) {
                swap(minIdx,index);
                index = minIdx;
            }else {
                break;
            }
        }
    }

    /**
     *        0
     *      1    2
     *    3   4
     *
     *    (4 - 1) / 2
     *
     * @param index
     */
    private void heapInsert(int index) {
        // 往上走
//        NodeTime parentNode = values[(index - 1) /2];
        while (index > 0) {
            int parentIdx = (index - 1) /2;
            if (values[parentIdx].times > values[index].times) {
                swap(parentIdx,index);
            }else {
                break;
            }
            index = parentIdx;
        }
    }

    private void swap(int x1,int x2) {
        NodeTime tmp = values[x1];
        values[x1] = values[x2];
        values[x2] = tmp;
        locations.put(tmp.key,x2);
        locations.put(values[x1].key,x1);
    }
}

public class _020_词频最大的K个数据结构 {

    public static void main(String[] args) {
        TopRecord topRecord = new TopRecord(3);
        topRecord.add("bac");
        topRecord.add("bbb");
        topRecord.add("ggg");
        topRecord.add("ccc");
        topRecord.add("ggg");
        topRecord.add("ccc");
        topRecord.add("bbb");
        topRecord.add("ggg");
        topRecord.add("bbb");

        List<String> top = topRecord.top();
        System.out.println(top);
    }
}
